1. Field of the Invention
The invention relates to the field of data processing systems. More specifically, the invention relates to exception processing and out-of-order execution in data processing systems.
2. Background Information
Performance of data processing systems may be improved by executing certain operations out-of-order, relative to in-order (i.e., original program order) execution (hereinafter, operation is used generally to refer to microoperations, macrooperations, instructions, etc.). For example, consider the following in-order sequence of operations in TABLE 1. As shown, the first column indicates the original program ordering of the operations in the sequence:
TABLE 1 ______________________________________ ORDER OPERATION DESCRIPTION ______________________________________ 1 LOAD [MEM1], X; Load value from memory to register X 2 LOAD [MEM2], Y; Load value from memory to register Y 3 INCR Z; Increment value of register Z 4 ADD Y, X; Add Y to X, place result in X 5 ADD Z, X; Add Z to X, place result in X 6 ST [MEM3], X; Store the result in X to memory ______________________________________
The first two operations in the sequence to be executed, operation 1 and operation 2 (loads from memory), may require similar (shared) resources, such as address decode logic, memory bus, etc. Moreover, operation 3 in the sequence (INCR Z) does not depend on the previous operations and may not require the same resources. Thus, operation 3 may be performed concurrently (at least in part) with operation 1 or operation 2, for example.
Thus, to achieve relatively greater parallelism, thereby improving efficiency, the in-order sequence shown in TABLE 1 may be scheduled to be executed out-of-order, as shown in the example of TABLE 2. As shown in TABLE 2, the third operation in the in-order sequence is scheduled to be executed immediately following the first operation to achieve relatively greater parallelism over execution of the in-order sequence shown in TABLE 1.
Machines that perform out-of-order execution may employ a mechanism to recover original program order subsequent to out-of-order execution. Typically, a reorder buffer (sometimes referred to as a reorder/retire queue/stack) is utilized to retire operations in original program order, subsequent to out-of-order execution. A reorder buffer may operate with some retirement/reorder logic, including, for example, a reorder stack pointer, to retire the operations in original program order. Thus, a reorder buffer may help recover original program order subsequent to out-of-order execution.
TABLE 2 ______________________________________ ORDER OPERATION DESCRIPTION ______________________________________ 1 LOAD [MEM1], X; Load value from memory to register X 3 INCR Z; Increment value of register Z 2 LOAD [MEM2], Y; Load value from memory to register Y 4 ADD Y, X; Add Y to X, place result in X 5 ADD Z, X; Add Z to X, place result in X 6 ST [MEM3], X; Store the result in X to memory ______________________________________
Unfortunately, not all operations may be executed out-of-order. In particular, operations that may cause exceptions and/or unrecoverable side effects may be limited to strict (in-order) program ordering. Operations that are limited to program (in-order) ordering are referred to as "architectural" operations. Typically, operations which result in side effects which may not be rolled back (i.e., undone) are considered as architectural operations (e.g., store issue to memory). In machines which utilize "architectural ordering," operations preceding architectural operations (in the original program order) may be executed out-of-order relative to each other, but should be executed prior to execution of the particular architectural operations. Moreover, architectural operations should typically be executed in strict program order with respect to other architectural operations in machines which utilize architectural ordering.
One example of an operation that is typically considered architectural is a store operation. It is apparent from the example sequence of operations shown in TABLEs 1 and 2 that the value that is stored by the store operation 6 depends on the completed result of the previous operations 1-5. Thus, if the store operation 6 is executed out-of-order relative to operations 1-5 that precede operation 6 in the sequence (e.g., executed between operations 3 and 4) an incorrect/incomplete value would be stored in the memory location [MEM3]. Accordingly, the store operation should be executed subsequent to operations 1-5.
Operations that may cause exceptions may also be considered architectural, since out-of-order execution of such operations may cause a "deadlock," which is described by way of the following example. Consider the sequence of operations in TABLEs 3 and 4:
TABLE 3 ______________________________________ ORDER OPERATION DESCRIPTION ______________________________________ 1 ST 1; Store operation 2 ST 2; Store operation 3 FP 1; (Excepting) Floating point operation ______________________________________
As shown in TABLE 3, the first two operations (ST 1 and ST 2) are store operations, and thus, may be considered architectural, and ordered accordingly (e.g., ST 2 may not be executed prior to ST 1). The third operation is a floating point operation that encounters an exception. To illustrate deadlock, consider first the case where FP 1 is not considered architectural, and thus, may be executed out-of-order. TABLE 4 illustrates this first case. As shown, FP 1 is re-ordered to be executed after ST 1 and before ST 2.
TABLE 4 ______________________________________ ORDER OPERATION DESCRIPTION ______________________________________ 1 ST 1; Store operation 3 FP 1; (Excepting) Floating point operation 2 ST 2; Store operation ______________________________________
In response to the exception caused by FP 1, the pipeline may be "flushed" upon execution of FP 1 (i.e., one or all of the operations following FP 1 would be aborted in the pipeline, which operation in the given example is ST 2). However, if the pipeline is flushed upon causing the exception encountered by FP 1, retirement logic may not be able to resume execution with FP 1 since ST 2 (which is architecturally ordered) has not yet been executed. Additionally, ST 2 will have been flushed. As a result, a state of "deadlock" may occur, in which state the data processing system is unable to determine at which operation execution is to resume without skipping over and/or re-executing one or more operations.
Although one technique to address the above-mentioned difficulties may be to always architecturally order operations that may cause exceptions (e.g., floating point operations), such a solution may significantly degrade performance. This is especially true, since certain excepting operations (i.e., operations that may cause an exception), such as floating point operations, may often lie within a routine's critical path.
Thus, it is desirable to allow one or more types of operations that may cause an exception to be scheduled out-of-order, while avoiding the above-described effects (e.g., deadlock).